package LimitedTimeGame.Day_0218;

/**
 * @author zxc
 * @date 2023/02/18 09:45
 **/

import java.util.Arrays;
import java.util.HashMap;

/**
 * 题目 ：单词频率
 * 题目详述 ：
 * 设计一个方法，找出任意指定单词在一本书中的出现频率。
 * 你的实现应该支持如下操作：
 * WordsFrequency(book)构造函数，参数为字符串数组构成的一本书
 * get(word)查询指定单词在书中出现的频率
 *
 * 提示：
 * book[i]中只包含小写字母
 * 1 <= book.length <= 100000
 * 1 <= book[i].length <= 10
 * get函数的调用次数不会超过100000
 *
 *
 */
public class WordsFrequency02 {
    /**
     * 思路 ：
     * 使用前缀树，将某个单词存储在前缀树中 && 同时，该前缀树的叶子节点去保存该单词出现次数;
     * @param book
     */
    PrefixTree root = new PrefixTree();
    public WordsFrequency02(String[] book) {
        for (String str : book) {
            PrefixTree temp = root;
            // 遍历当前字符串str中的每个字符 && 同时将其中的每个字符存储到前缀树中去;
            for (char ch : str.toCharArray()) {
                if(temp.children[ch - 'a'] == null){
                    PrefixTree node = new PrefixTree();
                    temp.children[ch - 'a'] = node;
                }
                temp = temp.children[ch - 'a'];
            }
            // 遍历当前字符串str结束后，当前temp节点所指向的是当前字符串str的最后一个字符;
            temp.count++;
        }
    }

    public int get(String word) {
        PrefixTree node = root;
        for (char ch : word.toCharArray()) {
            if(node.children[ch - 'a'] == null) {
                return 0;
            }
            node = node.children[ch - 'a'];
        }
        return node.count;
    }
    class PrefixTree{
        PrefixTree[] children;
        // 变量count，若不是0的话，则代表该字符为某个单词的结尾 && 同时记录了当前单词出现频率;
        public int count;
        public PrefixTree(){
            // 由于单词中只包含小写字母，所以前缀树中某个节点的chilren数组固定大小为26;
            children = new PrefixTree[26];
        }
    }
}
